1. Field of the Invention
The present invention relates to power-residue calculating units used for encryption and decryption of information applicable in the fields of telecommunications network, traffic, finance, medical services, distribution and so on. More particularly, the present invention relates to a power-residue calculating unit using a Montgomery algorithm.
2. Description of the Background Art
Owing to the technological development in the field of telecommunication, security (namely, to prevent criminal use or destruction of data) over a communication network has received a great deal of attention. Therefore, encryption and decryption of information are frequently used. The applicable fields of encryption and decryption range from telecommunication to traffic, finance, medical services, distribution and so on. This type of encryption and decryption are required to realize an advanced security based on a simple concept.
To facilitate understanding of this type of technique, a concept of encryption/decryption of information will be briefly described. In the world of encryption, “asymmetric cipher algorithm” is superior. The asymmetric cipher algorithm refers a cipher algorithm using different encryption and description keys, where one of which cannot be “easily calculated” from the other. An RSA (Rivest-Shamir-Adleman scheme) cipher using a power-residue calculation (a residue is obtained by multiplying a certain number X several times and then dividing the result by N) is representative of the asymmetric cipher algorithm.
Basically, the power-residue calculation is used in accordance with the following formula (1) to generate an RSA cipher. Formula (1) implies that a residue is obtained by dividing XY by N. In formula (1), X represents a plaintext to be subjected to encryption (decryption), where Y and N are keys for encryption (decryption).XYmodN  (1)
The power-residue calculation facilitates encryption and decryption of information. If the operand bit lengths of X, Y, and N are increased, decryption of each key becomes difficult.
However, the greater operand bit length requires a longer period of time for the power-residue calculation. Then, a major point is to reduce the time for the power-residue calculation with a greater operand bit length.
Next, encryption and decryption processes using the power-residue calculation will be described with an RSA cipher by way of example.
[Encryption and Decryption of RSA Cipher]
(1) For decryption of the RSA cipher, the following equation (2) is used.C=MemodN  (2)
For decryption, the following equation (3) is used.M=CdmodN  (3)
Here, M represents a plaintext for encryption, and C represents a plaintext which has been subjected to encryption, i.e., a ciphertext. Further, e and N in equation (2) are encryption keys, whereas d and N in equation (3) are decryption keys. There is a predetermined relationship between the following equations (4) and (5).N=p·q  (4)1≡e·dmod{LCM(p−1, q−1)}  (5)
Here, “≡” indicates that the left and right sides are similar to each other, and “LCM” is an abbreviation for a least common multiple. Further, p and q are relatively prime integers. Note that e and N are public keys, whereas d, p and q are secret keys.
Equations (4) and (5) both define conditions of numeric values for the power-residue calculation in a cipher algorithm. Equation (4) indicates that N is a product of relatively prime large prime numbers p and q. Since p and q are both odd numbers, n should also be an odd number. Equation (5) indicates that a residue, which is obtained by dividing a product of e and d by a least common multiple of values obtained by deducting 1 respectively from p and q shown in equation (4), is 1.
Under the conditions specified in equations (4) and (5), plaintext M is encrypted by equation (2), and encrypted plaintext M (ciphertext C) is decrypted by equation (3).
[Method of Power-Residue Calculation]
A method of a power-residue calculation used for encryption/decryption will now be described. The power-residue calculation for A=MemodN is carried out with use of an iterative square product method as shown in the following flow 1 with a binary digit expansion of an integer e being ek−1 . . . e1e0.
(Flow 1)
beginA=1for i=k−1 to 0                beginA=A2modN  (6)If ei=1 then A=A·MmodN  (7)        end        
end
A solution of the power-residue calculation would be equal to A.
As described above, the calculation is based on multiplication and division (mod calculation) as shown in equations (6) and (7). The multiplication provides A×A or A×M for a value of A having an initial value of 1. The division provides modN for a value obtained by each multiplication (a calculation of a residue when divided by N). Calculations are iteratively performed in accordance with a bit value of “e” with a pair of “multiplication and division” (A×AmodN, A×MmodN). More specifically, “multiplication and division” is performed in accordance with each bit starting from the most significant bit to the least significant bit of “e”.
As described above, in the power-residue calculation, a solution is obtained by iteratively performing basic residual calculations (mod calculation). The iterative frequency per se is at most several hundreds to several thousands of times, which can be well handled by a software. However, to carry out the residue calculation per se, i.e., division, by a hardware, a large calculation circuit and a complicated process are required, which should be preferably improved. Since large integers of about 1024 bits are usually used for e, d, M, N and so on, even a high-speed exponential calculation still requires multiple precision multiplication and residual calculation of about 1500 times on average per RSA calculation. In particular, various high-speed methods, including an approximation method, residual table method and Montgomery algorithm, have been proposed for the residual calculation.
To increase the speed of the power-residue calculation mostly used for a public key cryptograph representative of the RSA cipher, the speed of one residual calculation must be increased. A Montgomery algorithm provides high speed residual calculation. In particular, in the multiplication residual calculation, division can be simplified by e.g., bit shift. Thus, the power-residue calculation used for a public key cryptograph (e.g., RSA cipher) can be performed at higher speed.
On the other hand, the Chinese remainder theorem provides that a calculation with a composite number being a modulo can be carried out by a calculation where relatively prime factors of the composite number is a modulo. If this is applied to RSA encryption with 1024-bit length, in practice, only a calculating circuit with a modulo of an integer of a 512-bit length (here corresponding to p and q), rather than a power-residue calculating circuit with a modulo N of a 1024-bit length, is required as a hardware. This contributes to miniaturization of the hardware.
As described above, the size of the calculating circuit disadvantageously increases since the power-residue calculation involves a highly complicated process of basic residue calculation (mod calculation). Then, Montgomery has proposed that a solution can be obtained by “multiplication” and a simple bit-string process, rather than by the above described general method of residual calculation (mod calculation). The method proposed by Montgomery will be briefly described in the following.
[Montgomery Algorithm]
A Montgomery algorithm implementing high speed residual calculation will be described.
The Montgomery algorithm is based on the fact that use of residual modulo N (N>1) and a cardinal number R (R>N) which is relatively prime with respect to residual modulo N allows calculation of TR−1modN to be performed only by division by cardinal number R with a dividend being T. This eliminates the need for division by N for the residual calculation. Here, N, R, R−1 and T are integers. Dividend T satisfies 0≦T<R·N. R−1 is an inverse of cardinal number R according to residual modulo N. Further, consider an integer N′ that satisfies a relation of R·R−1−N·N′=1 (0≦R−1<N, 0≦N′<R). Further, if a power of 2 is used for cardinal number R, the division by cardinal number R can be replaced by a shift operation. Thus, a high speed calculation of T→TR−1modN (TR−1modN with a dividend being T) is enabled.
An algorithm MR (T) of T→TR−1modN is given below as algorithm 1. Note that in algorithm 1, (T+m·N)/R has been proved to be always devisable.
(Algorithm 1) Algorithm Y=MR (T) of T→TR−1modN is given by the following equations.M=(TmodR)·N′modR  (8)Y=(T+m·N)/R  (9)if Y≧N then Y=Y−NY<N then return Y
A single MR provides only TR−1modN rather than a residue TmodN. Thus, to find residue TmodN, an MR calculation is again performed using a product of MR (T) and preliminary found R2modN as shown below.MR(MR(T)·(R2modN)) =(TR−1modN)·(R2modN)·R−1modN=TR−1·R2·R−1modN=TmodN
Thus, residue TmodN can be found.
An algorithm implementing the multiplication residue calculation by the Montgomery method using the iterative square product method (iterative square method) of the power-residue calculation is given below. Search is performed starting from an upper bit of key e and, if the bit value of the key is 1, the Montgomery multiplication residual calculation of MR (X·Y) is performed.Y=Rr(Rr=R2modN(R=2k+2))X=MX=MR(X,Y)  (10)Y=MR(1·Y)  (11)for j=k to 1if ej==1 then Y=MR(X·Y)  (12)if j>1 then Y=MR(X·Y)  (13)
endY=MR(1·Y)  (14)Y=YmodN  (15)
Here, MR (X·Y) and MR (Y·X) are equal, where ej represents j-th bit of key e. In the case of an integer with 512-bit length, k=512. The power-residue calculation of 512 bits can be implemented by the Montgomery multiplication residue calculation of 514 bits and the residual calculation of 512 bits.
The Montgomery multiplication residual calculation result P=MR (B·A) is found in the following manner by a sequential calculation of a cardinal number W which is most suitable for being implemented as a hardware.
 W=2dN0′=N′modWP=0for j=0 to kM=(PmodW)·N0′  (16)P=((P+(AmodW)·B·W+M·N)/W)mod2k  (17)A=A/W  (18)
end
Here d is a natural number depending on the hardware. Thus, Montgomery multiplication residual calculation result P can be found. Then, 514-bit Montgomery multiplication residual calculation result P=MR (B·A) can be found in the following manner by a sequential calculation of cardinal number 2 where d=1.N0′=N′mod2P=0for j=0 to 514M=(Pmod2)·N0′  (19)P=((P+(Amod2)·B·2+M·N)/2)mod2514  (20)A=A/2  (21)
end
As described above, to implement the power-residue calculation, a common practice is to use the Montgomery method for the 512-bit power-residue calculation in the hardware and to use a process making use of the Chinese remainder theorem in the hardware. There are a plurality of methods of implementing to the hardware, which may be employed in practice.
However, in a conventional circuit, a process is performed as shown in FIG. 8. More specifically, a hardware with a circuit making use of the Montgomery method for the 512-bit power-residue calculation is used and equations (10) to (18) are directly carried out. For example, equation (12) is omitted if ej==0. On the other hand, calculation (17) is always carried out. Thus, a complicated process is required and hence higher calculation speed is desired. In addition, since the demands for circuits which is reduced in size and is suitable for an LSI (Large Scale Integration) have been on the increase, the operation process must be simplified as much as possible to reduce the overall calculation amount for higher processing speed.